package BST;

import java.security.KeyPair;


class Node<T extends Comparable<T>>
{
	T _val;
	Node<T> _rchildNode;
	Node<T> _lchildNode;
	
	public Node(T val)
	{
		_val = val;
		_rchildNode = null;
		_lchildNode = null;
	}
}

class BSTree<T extends Comparable<T>>
{
	Node<T> rootNode;
	
	public Node<T> find(T val)
	{
		Node<T> curNode = rootNode;
		
		try {
            while (curNode != null) {
                if (val.compareTo(curNode._val) < 0) {
                    curNode = curNode._lchildNode;
                } else if (val.compareTo(curNode._val) > 0) {
                    curNode = curNode._rchildNode;
                } else {
                	System.out.println("找到了"+val);
                    return curNode;
                }
            }
        } catch (NullPointerException e) {
            System.err.println("Null pointer exception occurred during find operation: " + e.getMessage());
        } catch (ClassCastException e) {
            System.err.println("Class cast exception occurred during find operation: " + e.getMessage());
        }
		
		//System.out.println("没找到"+val);
		return null;
	}
	
	public boolean add(T val)
	{
		try {
		if(rootNode == null)//空树特殊处理
		{
			rootNode = new Node<T>(val);
			return true;
		}
		
		Node<T> ret = find(val);
		if(ret != null)//已经有了直接返回
			{
			//System.out.println("jjj");
			return false;
			}
		else //没有就开始插入
		{
			//System.out.println("jjj");
			Node<T> curNode = rootNode;
			Node<T> parentNode = null;
			while(curNode != null)
			{
				parentNode = curNode;
				if(val.compareTo((T) curNode._val) < 0)
				{
					curNode = curNode._lchildNode;
				}
				else
				{
					curNode = curNode._rchildNode;
				}
			}
			//System.out.println("parent" + parentNode._val);
			
			Node<T> newnode = new Node<T>(val);
			
			if(val.compareTo((T) parentNode._val) < 0)
			{
				parentNode._lchildNode = newnode;
			}
			else
			{
				parentNode._rchildNode = newnode;
			}
			//System.out.println("new" + newnode._val + "------");
		
			return true;
		}	
		}
		catch (NullPointerException e) {
            System.err.println("Null pointer exception occurred during add operation: " + e.getMessage());
        } catch (ClassCastException e) {
            System.err.println("Class cast exception occurred during add operation: " + e.getMessage());
        }
		
		return false;
		
	}
	
	
	public boolean delete(T val)
	{
		try {
		System.out.println("delete");
		if(rootNode == null)
			return false;
		
		Node<T> ret = find(val);
		
		if(ret == null)//不存在该值
			return false;
		
		Node<T> curNode = rootNode;
		Node<T> parentNode = null;
		//System.out.println("没进循环");
		while(curNode != null)
		{
			//System.out.println("进了循环");
			if(val.compareTo(curNode._val) < 0)
			{
				parentNode = curNode;
				curNode = curNode._lchildNode;
			}
			else if(val.compareTo(curNode._val) > 0)
			{
				parentNode = curNode;
				curNode = curNode._rchildNode;
			}
			else //找到了
			{
				//System.out.println("找到了");
				//System.out.println("curNode" + curNode._val);
				//System.out.println("PNode" + parentNode._val);
				if(curNode._lchildNode == null)//左子树为空
				{
					System.out.println("左子树空");
					if(parentNode == null)//根节点特判
					{
						rootNode = curNode._rchildNode;
						return true;
					}
					
					if(curNode == parentNode._rchildNode)
					{
						
						parentNode._rchildNode = curNode._rchildNode;
					}
					else 
					{
						System.out.println("是父亲节点的左边");
						parentNode._lchildNode = curNode._rchildNode;
					}
					
					return true;
				}
				else if(curNode._rchildNode == null)//右子树为空
				{ 
					System.out.println("右子树空");
					
					if(parentNode == null)//根节点特判
					{
						rootNode = curNode._lchildNode;
						return true;
					}
					
					if(curNode == parentNode._lchildNode)
					{
						parentNode._lchildNode = curNode._lchildNode;
					}
					else 
					{
						parentNode._rchildNode = curNode._lchildNode;
					}
					
					return true;
				}
				else //左右子树都不为空
				{
					Node<T> rminNode = curNode._rchildNode;
					Node<T> rminparnetNode = curNode;//防止右子树只有一个节点
					while(rminNode._lchildNode != null)//找右边最小的节点
					{
						rminparnetNode = rminNode;
						rminNode = rminNode._lchildNode;
					}
					
					T tmp = rminNode._val;
					rminNode._val = curNode._val;
					curNode._val = tmp;
					
					
					rminparnetNode._lchildNode = rminNode._rchildNode;
					
				
					return true;
				}
				
			}
			
			
		}
		//System.out.println("？？？");
		return true;
		}
		 catch (NullPointerException e) {
	            System.err.println("Null pointer exception occurred during delete operation: " + e.getMessage());
	        } catch (ClassCastException e) {
	            System.err.println("Class cast exception occurred during delete operation: " + e.getMessage());
	        }
	        return false;
		
	}
	
	
	public void PREVORDER(Node<T> root)
	{
		if(root == null)
			return;
		
		PREVORDER(root._lchildNode);
		System.out.println(root._val);
		PREVORDER(root._rchildNode);
	}
	
	public void PrevOrder()
	{
		//System.out.println(rootNode._val);
		PREVORDER(rootNode);
	}
}

public class BST {

	public static void main(String[] args) {
		BSTree<Integer> t = new BSTree<Integer>();
		
		t.add(15);
		t.add(6);
		t.add(3);
		t.add(2);
		t.add(4);
		t.add(7);
		t.add(13);
		t.add(9);
		t.add(18);
		t.add(17);
		t.add(20);
		
		t.find(9);
		t.find(8);
		
		t.delete(15);
		
		t.PrevOrder();
		

	}

}
